﻿/*
题目：找出出现至少三次的最长特殊子字符串 II

给你一个仅由小写英文字母组成的字符串 s 。

如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。

返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。

子字符串 是字符串中的一个连续 非空 字符序列。

https://leetcode.cn/problems/find-longest-special-substring-that-occurs-thrice-ii/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    // **KEY** 子字符串问题，采用滑动窗口，以 i 当前字母为结尾字母，就可以来统计所有满足题意的字符串
    // 求连续 x 最少出现三次的最长
    int maximumLength(string s) {
        // 子字符串，所以考虑使用滑动窗口
        int left = 0;
        unordered_map<string, int> mp;      // 所有特殊字符串出现的次数
        char win = 'A';                     // 当前窗口的特殊字符
        int maxlen = -1;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] != win) {
                left = i;
                win = s[i];
            }

            // 相等，那么需要将以 i 结尾的所有特殊字符串 结算一下
            for (int k = left; k <= i; k++) {
                int len = i - k + 1;
                if (++mp[s.substr(k, len)] == 3) {
                    maxlen = max(maxlen, len);
                }
            }
        }

        return maxlen;
    }

    // 求连续 x 最少出现三次的最长
    int maximumLengthUpgrade(string s) {
        // 子字符串，所以考虑使用滑动窗口
        int left = 0;
        unordered_map<char, int> satisfied;                     // 以 char 为根的特殊字符串，并出现了 3 次，满足题意的最长长度

        unordered_map<char, unordered_map<int, int>> mp;        // 所有特殊字符串出现的次数  
        char win = 'A';                                         // 当前窗口的特殊字符
        int maxlen = -1;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] != win) {
                left = i;
                win = s[i];
            }
            if (satisfied[win] >= i - left + 1)
                continue;


            // 相等，那么需要将以 i 结尾的所有特殊字符串 结算一下
            for (int k = left; k <= i; k++) {
                int len = i - k + 1;
                if (satisfied[win] >= len)
                    break;

                if (++mp[win][len] == 3) {
                    maxlen = max(maxlen, len);
                    satisfied[win] = max(satisfied[win], maxlen);       // 该字符代表的出现了三次的字符串，更新最大长度
                }
            }
        }

        return maxlen;
    }
};
